package hyy_2022;

/**
 * 连续子数组的最大和
 * f(i) 代表以第i个数结尾的【连续子数组的最大和】
 * f(i) 只和f(i-1)有关, 用一个变量pre来维护对于当前f(i)的f(i-1)的值是多少
 */
public class _0808_Offer42_MaxSubArray {

    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for(int x : nums) {
            pre = Math.max(pre+x,x);
            maxAns = Math.max(maxAns,pre);
        }
        return maxAns;
    }
}
